class Solution
{
public:
    vector<vector<int>> ret;
    vector<int> path;
    int _n, _k;
    void dfs(int pos)
    {
        if (path.size() == _k)
        {
            ret.push_back(path);
            return;
        }
        for (int i = pos; i <= _n; ++i)
        {
            path.push_back(i);
            dfs(i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k)
    {
        _n = n;
        _k = k;
        dfs(1);
        return ret;
    }
};
class Solution
{
public:
    int findTargetSumWays(vector<int> &nums, int target)
    {
        // int sum = 0;
        // for(auto e : nums)
        //     sum += e;
        // int num = (sum + target) / 2;
        // if(num < 0 || (sum + target)%2 ==1) return 0;
        // int n = nums.size();
        // vector<vector<int>> dp(n+1,vector<int>(num+1));
        // dp[0][0] = 1;
        // for(int i=1;i<=n;++i)
        // {
        //     for(int j=0;j<=num;++j)
        //     {
        //         dp[i][j] = dp[i-1][j];
        //         if(j >= nums[i-1])
        //             dp[i][j] += dp[i-1][j-nums[i-1]];
        //     }
        // }
        // return dp[n][num];

        int sum = 0;
        for (auto e : nums)
            sum += e;
        int num = (sum + target) / 2;
        if (num < 0 || (sum + target) % 2 == 1)
            return 0;
        int n = nums.size();
        vector<int> dp(num + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = num; j >= nums[i - 1]; --j)
            {
                dp[j] += dp[j - nums[i - 1]];
            }
        }
        return dp[num];
    }
};
class Solution
{
public:
    int ret;
    int aim;
    // int path;
    void dfs(vector<int> &nums, int pos, int path)
    {
        if (pos == nums.size())
        {
            if (path == aim)
            {
                ++ret;
                return;
            }
        }
        else
        {
            dfs(nums, pos + 1, path + nums[pos]);
            dfs(nums, pos + 1, path - nums[pos]);
        }

        // // pos位置数前面是加号
        // path += nums[pos];
        // dfs(nums,pos+1);
        // path -= nums[pos];//恢复现场

        // // pos位置数前面是减号
        // path -= nums[pos];
        // dfs(nums,pos+1);
        // path += nums[pos];//恢复现场
    }
    int findTargetSumWays(vector<int> &nums, int target)
    {
        aim = target;
        dfs(nums, 0, 0);
        return ret;
    }
};
class Solution
{
public:
    vector<vector<int>> ret;
    vector<int> path;
    void dfs(vector<int> &nums, int pos)
    {
        if (pos == nums.size())
        {
            ret.push_back(path);
            return;
        }
        // 选pos位置数据
        path.push_back(nums[pos]);
        dfs(nums, pos + 1);
        path.pop_back(); // 恢复现场

        // 不选pos位置数据
        dfs(nums, pos + 1);
    }
    vector<vector<int>> subsets(vector<int> &nums)
    {
        dfs(nums, 0);
        return ret;
    }
};